package com.lsa.letcode.the109.sortedListToBst;

import com.lsa.letcode.common.ListNode;
import com.lsa.letcode.common.TreeNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
    	if (head == null){
    		return null;
    	}
        return sortedListToBST(new ListNode[]{head}, 0, size(head) - 1);
    }
    
    private int size(ListNode head) {
    	int size = 0;
    	while(head != null) {
    		size++;
    		head = head.next;
    	}
		return size;
	}
    
    private TreeNode sortedListToBST(ListNode[] head, int from, int to){
    	if (from > to){
    		return null;
    	}
    	
    	int mid = (from + to) >>> 1;
    	TreeNode left = sortedListToBST(head, from, mid - 1);
    	
//    	if (left != null){
//    		Node<Integer> t1 = TreeUtils.copyAdaptTree(left);
//    		System.out.println(BinaryTreeUtils.toString(t1));
//    	}
//    	else {
//    		System.out.println("null left");
//    	}
//    	System.out.print(head[0].val + " ");
    	TreeNode n = new TreeNode(head[0].val);
    	head[0] = head[0].next;
    	TreeNode right = sortedListToBST(head, mid + 1, to);
//    	if (right != null){
//    		Node<Integer> t1 = TreeUtils.copyAdaptTree(right);
//    		System.out.println(BinaryTreeUtils.toString(t1));
//    	}
//    	else {
//    		System.out.println("null right");
//    	}
    	n.left = left;
    	n.right = right;
    	return n;
    }

	@SuppressWarnings("unused")
	private TreeNode sortedListToBST2(ListNode head, ListNode iter, int cur, int left) {
		if (left < 1){
			return null;
		}
		else if (cur >= left) {
			TreeNode n = new TreeNode(iter.val);
			n.left = sortedListToBST2(head, head, 1, cur - 1);
			n.right = sortedListToBST2(iter.next, iter.next, 1, left - 1);
			return n;
		}
		else {
			return sortedListToBST2(head, iter.next, cur + 1, left - 1);
		}
	}
}